// Package can_t_ac_hard 1-42
// @Title can_t_ac_hard
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/9 10:35
// @Create  2021/9/9 10:35
package no_ac_hard

// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

// 暴力解决接雨水问题  时间 O(N*N) 空间 O(1)
func TrapViolence(height []int) int {
	var ans int
	size := len(height) // 获取数组长度
	for i := 1; i < size-1; i++ {
		max_left, max_right := 0, 0
		for j := i; j >= 0; j-- { // 搜索左边最小的值
			max_left = max(max_left, height[j])
		}
		for k := i; k < size; k++ { // 搜索右边
			max_right = max(max_right, height[k])
		}
		ans += min(max_left, max_right) - height[i]
	}
	return ans
}

/**
找到数组中从下标 i 到最左端最高的条形块高度 left_max。
找到数组中从下标 i 到最右端最高的条形块高度 right_max。
扫描数组 \text{height}height 并更新答案：
累加 \min(\text{max\_left}[i],\text{max\_right}[i]) - \text{height}[i]min(max_left[i],max_right[i])−height[i] 到 ansans 上

*/
// 动态规划解决接雨水问题  时间 O(N) 空间 O(N)
func TrapDP(height []int) int {
	if height == nil {
		return 0
	}
	ans := 0
	size := len(height)
	left_max_arr := make([]int, size)
	right_max_arr := make([]int, size)
	left_max_arr[0] = height[0]
	for i := 1; i < size; i++ {
		left_max_arr[i] = max(height[i], left_max_arr[i-1])
	}
	right_max_arr[size-1] = height[size-1]
	for i := size - 2; i >= 0; i-- {
		right_max_arr[i] = max(height[i], right_max_arr[i+1])
	}
	for i := 1; i < size-1; i++ {
		ans += min(left_max_arr[i], right_max_arr[i]) - height[i]
	}
	return ans
}

// 单调栈解决接雨水问题  时间 O(N) 空间 O(N)
func TrapMonotonousStack(height []int) int {
	var ans int
	current := 0
	stact := make([]int, 0)
	for current < len(height) {
		for len(stact) > 0 && height[current] > height[stact[len(stact)-1]] {
			top := stact[len(stact)-1]
			stact = stact[:len(stact)-1]
			if len(stact) <= 0 {
				break
			}
			distance := current - stact[len(stact)-1] - 1
			bounded_height := min(height[current], height[stact[len(stact)-1]]) - height[top]
			ans += distance * bounded_height
		}
		stact = append(stact, current)
		current++
	}
	return ans
}

// 双指针解决接雨水问题  时间 O(N) 空间 O(1)  ------>>>>>>> 最优解
func TrapTwoPoint(height []int) int {
	l, r := 0, len(height)-1
	ans := 0
	l_max, r_max := 0, 0
	for l < r {
		if height[l] < height[r] {
			if height[l] >= l_max {
				l_max = height[l]
			} else {
				ans += l_max - height[l]
			}
			l++
		} else {
			if height[r] > r_max {
				r_max = height[r]
			} else {
				ans += r_max - height[r]
			}
			r--
		}
	}
	return ans
}
